/***************************************************************************
 *  Title: Kernel Memory Allocator
 * -------------------------------------------------------------------------
 *    Purpose: Kernel memory allocator based on the resource map algorithm
 *    Author: Stefan Birrer
 *    Copyright: 2004 Northwestern University
 ***************************************************************************/
/***************************************************************************
 *  ChangeLog:
 * -------------------------------------------------------------------------
 *    Revision 1.2  2009/10/31 21:28:52  jot836
 *    This is the current version of KMA project 3.
 *    It includes:
 *    - the most up-to-date handout (F'09)
 *    - updated skeleton including
 *        file-driven test harness,
 *        trace generator script,
 *        support for evaluating efficiency of algorithm (wasted memory),
 *        gnuplot support for plotting allocation and waste,
 *        set of traces for all students to use (including a makefile and README of the settings),
 *    - different version of the testsuite for use on the submission site, including:
 *        scoreboard Python scripts, which posts the top 5 scores on the course webpage
 *
 *    Revision 1.1  2005/10/24 16:07:09  sbirrer
 *    - skeleton
 *
 *    Revision 1.2  2004/11/05 15:45:56  sbirrer
 *    - added size as a parameter to kma_free
 *
 *    Revision 1.1  2004/11/03 23:04:03  sbirrer
 *    - initial version for the kernel memory allocator project
 *
 ***************************************************************************/
#ifdef KMA_RM
#define __KMA_IMPL__

/************System include***********************************************/
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h> // memcpy

/************Private include**********************************************/
#include "kma_page.h"
#include "kma.h"

/************Defines and Typedefs*****************************************/
/*  #defines and typedefs should have their names in all caps.
 *  Global variables begin with g. Global constants with k. Local
 *  variables should be in all lower case. When initializing
 *  structures and arrays, line everything up in neat columns.
 */
#define ALLOCATION_MASK   0x80000000
#define ALLOCATION_UNMASK 0x7FFFFFFF
#define FREE_MASK         0xF0000000
#define FREE_UNMASK       0x0FFFFFFF
#define NEXTPTR           0x0FFFFFFF
// DEBUG = 0 not include all printf functions to 
// print out the necessary information to debug the program
#define DEBUG             0

// a structure modified to add a pointer (KmaPageL) 
// to keep track of all get_page() dynamic memory allocated varaibles
typedef struct kmaPageT
{
   int id;
   void* ptr;
   struct kmaPageT* pKmaPageL;
} kma_page_tm;

// structure of all variables saved on the first page
typedef struct pageFree_List
{
   kma_page_tm* pLatestPage; // keep the recently latest page, used when 
   void* pFirst;             // free list pointers
   void* pLast;              // free list pointers
   void* pNext;              // a pointer to the unallocated area
   kma_size_t pageNo;        // number of pages requested
   kma_size_t memRemain; // if the remaining memory = 0, get_page()
   //int noPage; // number of pages requested
} pageFreeList;

// the header of the allocated memory
typedef struct header_all
{
   kma_size_t size; 
} headerA;

// the header of the freed memory
typedef struct header_fr
{
   kma_size_t size;
   void* pPrev;
   void* pNext;
} headerF;

/************Global Variables*********************************************/
static kma_page_t* pgFirstPage = NULL;
#if DEBUG
static int lineNo = 1;
#endif
/************Function Prototypes******************************************/

/************External Declaration*****************************************/

/**************Implementation***********************************************/
// Julia Zelenski approach to round up a number to be a multiple of 8
// NOTE: mult has to be power of 2 for this trick to work!
static inline kma_size_t roundup8(kma_size_t sz)
{
   return (sz + 7) & ~(7);
}

// return the roundedup size of the actual memory block
inline kma_size_t actualBlockSize(kma_size_t sz)
{
   return (sz + (sizeof(kma_size_t) << 1)  + 7) & ~(7);
}

// set the header mask to the size of the header
static inline kma_size_t setHeaderMask(kma_size_t sz)
{
   return sz | ALLOCATION_MASK;
}

// get rid of the mask from the size of the header
static inline kma_size_t setHeaderUnmask(kma_size_t sz)
{
  return sz & ALLOCATION_UNMASK;
}

// set the free mask to the size of the free memory block
static inline kma_size_t setFreeMask(kma_size_t sz)
{
   return sz | FREE_MASK;
}

// eliminate the mask from the size of the free memory block
static inline kma_size_t setFreeUnmask(kma_size_t sz)
{
  return sz & FREE_UNMASK;
}

// Free List Functions 
// Delete the memory block from the free list
static void FreeListDelete(headerF* pDelete)
{
   pageFreeList* pfl = pgFirstPage->ptr;
   if((pfl->pFirst == pDelete) && (pfl->pLast == pDelete))
   {  // the only one block in the list
      pfl->pFirst = NULL;
      pfl->pLast = NULL;
   } else if(pfl->pFirst == pDelete)
   {  // pFirst pDelete b1 b2 ....
      pfl->pFirst = pDelete->pNext;
      ((headerF*)(pDelete->pNext))->pPrev = &(pfl->pFirst);
   } else if(pfl->pLast == pDelete)
   {  // ... b1 b2 pDelete pLast
      pfl->pLast = pDelete->pPrev;
      ((headerF*)(pDelete->pPrev))->pNext = &(pfl->pLast);
   } else
   {  // pdPrev pDelete pdNext
      headerF* pdNext = pDelete->pNext;
      headerF* pdPrev = pDelete->pPrev;
      pdPrev->pNext = pdNext;
      pdNext->pPrev = pdPrev;
   }
   
   // reset the pointer from the free list
   pDelete->pNext = NULL;
   pDelete->pPrev = NULL;
   return;
}

// adopt the first fit algorithm. We search for the free list 
// and pull it out of the free list when its size is larger than
// size of the allocated memory block
static headerA* FreeListSearch(kma_size_t sz)
{  // find the free memory block in the free list
   pageFreeList* pfl = pgFirstPage->ptr;
   headerF* memBlock = (headerF*)pfl->pLast;
   if(memBlock != NULL)
   { // remember the first fit algorithm
     void* pFirst = &(pfl->pFirst);
     while(((void*)memBlock != pFirst) && (sz > setFreeUnmask(memBlock->size)))
	 memBlock = memBlock->pPrev;

     if((void*)memBlock == pFirst)
	 return NULL; // cannot find the appropriated size
      else
      {
	 FreeListDelete(memBlock); // found it, and return it.
	 return (headerA*)memBlock;
      }
   } else
      return NULL; // nothing in the list
}

// insert the free memory block to the free list 
static void FreeListInsert(void* ptr, kma_size_t size)
{  
   pageFreeList* pfl = (pageFreeList*)pgFirstPage->ptr;
   headerF* newfBlock = (headerF*)ptr;
   if((pfl->pFirst == NULL) && (pfl->pLast == NULL))
   {  // there is nothing in the free list
      pfl->pFirst = ptr;
      pfl->pLast = ptr;
      newfBlock->pPrev = &(pfl->pFirst);
      newfBlock->pNext = &(pfl->pLast);
   } else
   {
      headerF* pfblockl = pfl->pLast;
      while(((void*)pfblockl != &pfl->pFirst) && 
	    ((void*)newfBlock > (void*)pfblockl))
      { // sort the base ptr
	// first -> high base ptr -> next prev <- low base ptr <- last
	 pfblockl = pfblockl->pPrev;
      }
      
      if(&(pfl->pFirst) == (void*)pfblockl) 
      {  // higher first = pfblockl -> newfBlock b1 <- last
	 newfBlock->pNext = pfl->pFirst;
	 newfBlock->pPrev = &(pfl->pFirst);
	 ((headerF*)(pfl->pFirst))->pPrev = newfBlock;
	 pfl->pFirst = newfBlock;
      } else if(pfl->pLast == pfblockl)
      {  // higher first -> b1 newfBlock <- pfblockl = last
	 newfBlock->pNext = &(pfl->pLast);
	 newfBlock->pPrev = pfl->pLast;
	 ((headerF*)(pfl->pLast))->pNext = newfBlock;
	 pfl->pLast = newfBlock;
      } else 
      {  // higher first -> b1 pfblockl newfBlock b2 <- last
	 newfBlock->pNext = pfblockl->pNext;
	 newfBlock->pPrev = pfblockl;
	 ((headerF*)(pfblockl->pNext))->pPrev = newfBlock;
	 pfblockl->pNext = newfBlock;
      }
   }

   return;
}

#if DEBUG
// print the free list for the debugging purpose
static void printFreeList()
{
   if(pgFirstPage != NULL)
   {
      pageFreeList* pfl = pgFirstPage->ptr;
      printf("##### Start PrintFreeList #####\n");

      // print the first and last pointer first
      if((pfl->pFirst == NULL) || (pfl->pLast == NULL))
      {
	 printf("First: %p ||  Last: %p\n", pfl->pFirst, pfl->pLast);
	 return;
      } else 
      {
	 printf("%%%%%% High to Low Order %%%%%%\n");
	 printf("First: &%p Ptr: %p Size: %x\n", 
		&(pfl->pFirst), pfl->pFirst, ((headerF*)(pfl->pFirst))->size); 
	 printf("Last:  &%p Ptr: %p Size: %x \n", 
		&(pfl->pLast), pfl->pLast,((headerF*)(pfl->pLast))->size);

	 int i = 0;
	 headerF* pfblock = pfl->pFirst;
   
	 do
	 { // print other freed blocks of memory
	    i++;
	    printf("i: %d | %p | Size: %x | Prev: %p | Next: %p\n", 
		   i, pfblock, pfblock->size, pfblock->pPrev, pfblock->pNext);
	    pfblock = pfblock->pNext;
	 } while ((void*)pfblock != (void*)&(pfl->pLast)); 
      }
      printf("##### End PrintFreeList #####\n");
   }
}
#endif
// End Free List Functions

// malloc the memory in the program 
void* kma_malloc(kma_size_t size)
{
#if DEBUG
   lineNo++;
#endif
   kma_size_t memBlockSize = actualBlockSize(size);
#if DEBUG
   printf("\n\nLn: %d | malloc size: %x | blocksize: %x\n", lineNo,  size, memBlockSize);
#endif

   // According to the project requirement, if the memBlockSize is larger than PAGESIZE
   // return NULL.
   if(memBlockSize >= PAGESIZE)
      return NULL;

   pageFreeList* fl = NULL;
   headerA* header = NULL;
   kma_size_t* footer = NULL;
   if(pgFirstPage == NULL)
   {  // initialize the fields of the pageFreeList such as first, last, next, memRemain
      pgFirstPage = get_page();
      // set the size to be zero which is the null pointer
      ((kma_page_tm*)pgFirstPage)->pKmaPageL = NULL; 
      fl = (pageFreeList*) pgFirstPage->ptr;
      fl->pLatestPage = (kma_page_tm*)pgFirstPage;
      void* afterStFl = (headerA*)((char*)fl + sizeof(pageFreeList));
      fl->pNext = (char*)afterStFl + memBlockSize;
      *(int*)(fl->pNext) = NEXTPTR; // mark sth on memory NOTNECCESSARY
      fl->pFirst = NULL;
      fl->pLast = NULL;
      fl->memRemain = PAGESIZE - sizeof(pageFreeList) - memBlockSize;
      fl->pageNo = 1;
      header = (headerA*) afterStFl;
   } else
   {
      fl = (pageFreeList*) pgFirstPage->ptr;
      // search for the first free list 
      header = FreeListSearch(memBlockSize);
      if(header == NULL)
      {
	 kma_size_t remainMem = fl->memRemain;
	 if(remainMem > memBlockSize)
	    // if the request size is less then the remaining memory, 
	    // return it and update the memRemain.
	    fl->memRemain = remainMem - memBlockSize;
	 else
	 {  // Otherwise, get a new page and update memRemain
	    kma_page_tm* pNewPage = (kma_page_tm*) get_page();
	    pNewPage->pKmaPageL = fl->pLatestPage;
	    fl->pLatestPage = pNewPage;
	    fl->memRemain = remainMem - memBlockSize + PAGESIZE;
	    (fl->pageNo)++;
	 }
	 // update the next pointer 
	 header = (headerA*)fl->pNext;
	 fl->pNext = (char*)fl->pNext + memBlockSize;
	 *(int*)(fl->pNext) = NEXTPTR;
	 
      } else // if the memblock is pulled off from the list, use its size
	memBlockSize = setFreeUnmask(header->size);
   }
   // No freelists, return the address of the next pointer + sizeof(kma_size_t)
   kma_size_t headerSize = setHeaderMask(memBlockSize);
   header->size = headerSize;
   footer = (kma_size_t*)((char*)header + memBlockSize - sizeof(kma_size_t));
   *footer = headerSize;

#if DEBUG
   printFreeList(); // DEBUG
   printf("malloc: Base: %p Size: %x\n", (char*)header + sizeof(kma_size_t), header->size);
#endif

   return (char*)header + sizeof(kma_size_t);   

   // What to do
   // Check id if id is equal to more than MAXPAGES, return NULL;
}

// check whether the left hand size memory block is free or not
// for the coaleaceLeft only
static bool isFreeL(void* ptr)
{  // If it is free, the MSB = 0 and return true.
   // for the coaleaceLeft
   if((*(kma_size_t*)((char*)ptr - sizeof(kma_size_t)) & FREE_MASK) == FREE_MASK)
      return TRUE;
   else 
      return FALSE;
}

// coaleace the memory block on the left hand side
static kma_size_t coaleaceLeft(void** ptr, kma_size_t size)
{
   assert(ptr != NULL); // op
   headerF* nptr = *(void**)ptr;
   bool coaleace = FALSE;
   coaleace = isFreeL(nptr);
#if DEBUG
   int i = 0;
#endif
   while(isFreeL(nptr))
   {  // get a adjacent block on the left handside
#if DEBUG
      printf("\t coaleaceLeft -------- i = %d size = %x ----------\n", i++, size);
#endif
      kma_size_t szLeft = setFreeUnmask(*(kma_size_t*)((char*)nptr - sizeof(kma_size_t)));
      nptr = (headerF*)((char*)nptr - szLeft); // nptr points to the head of the coaleased block
      // get the block from the free list and rearrange the pointers
      FreeListDelete(nptr);
      size = size + szLeft; // enlarge the size of the coaleaced memory block
   } 

   if(coaleace)
   { // if there is a adjacent free block
      // void *memcpy(void *dest, const void *src, size_t n)
      kma_size_t freeMask = setFreeMask(size);
      memcpy(nptr, &freeMask, sizeof(kma_size_t)); // write a new size to the header
      // write a new size to the footer
      memcpy((char*)nptr + size - sizeof(kma_size_t), &freeMask, sizeof(kma_size_t)); 
      *(void**)ptr = nptr; // let the ptr pointer of kma_free save a new pointer after coaleacing
   }
   return  size;
}

// check whether the memory block on the right hand side is free or not 
// for the coaleaceRight only
static bool isFreeR(void* ptr)
{  // If it is free, the MSB = 0 and return true
   // for the coaleaceRight.
   if((*(kma_size_t*)((char*)ptr) & FREE_MASK) == FREE_MASK)
      return TRUE;
   else 
      return FALSE;
}

// coaleace the memory block on the right hand side
static kma_size_t coaleaceRight(void** ptr, kma_size_t size)
{
   assert(ptr != NULL);
   headerF* nptr = *(void**)ptr;
   headerF* dptr = (headerF*)((char*)nptr + size);

   bool coaleace = FALSE;
   coaleace = isFreeR(dptr);
#if DEBUG
   int i = 0;
#endif
   while(isFreeR(dptr))
   {  // get a adjacent block on the right handside
#if DEBUG
      printf("\t coaleaceRight -------- i = %d size = %x ----------\n", i++, size);
#endif
      kma_size_t szRight = setFreeUnmask(dptr->size);
      // dptr points to the head of the coaleased block
      // get the block from the free list and rearrange the pointers
      FreeListDelete(dptr);
      dptr = (headerF*)((char*)dptr + szRight);
      size = size + szRight; // enlarge the size of the coaleaced memory block
   } 

   if(coaleace)
   {  // if there is a adjacent free block
      // void *memcpy(void *dest, const void *src, size_t n)
      kma_size_t freeMask = setFreeMask(size);
      memcpy(nptr, &freeMask, sizeof(kma_size_t)); // write a new size to the header
      // write a new size to the footer
      memcpy((char*)nptr + size - sizeof(kma_size_t), &freeMask, sizeof(kma_size_t)); 
      *(void**)ptr = nptr; // let the ptr pointer of kma_free save a new pointer after coaleacing
   }
   return  size;
}

// free the memory according to the ptr and size
void kma_free(void* ptr, kma_size_t size)
{
   assert(ptr != NULL); // OP delete
#if DEBUG
   lineNo++; // DEBUG
#endif
   headerA* pfb = (headerA*)((char*)ptr - sizeof(kma_size_t));
   size = setHeaderUnmask(pfb->size);
#if DEBUG
   printf("\n\nLn: %d | free: base: %p, size: %x\n", lineNo, ptr, size);
#endif
   ptr = (char*)ptr - sizeof(kma_size_t);
   // DEBUG Concept blocksize
   

   if(size < sizeof(headerF) + sizeof(kma_size_t))
      // if the size is less than the sizeof(headerF) + sizeof(kma_size_t), do nothing.
      return;

   // start to coaleace on the left handside and then on the right handside
   size = coaleaceLeft(&ptr, size);
   size = coaleaceRight(&ptr, size);

   if(*(int*)((char*)ptr + size) == NEXTPTR)
   {  // free the block adjacent to the next pointer
      pageFreeList* pfl = pgFirstPage->ptr;
      pfl->pNext = ptr;
      *(int*)(ptr) = NEXTPTR;
      pfl->memRemain += size;

      while(pfl->memRemain > PAGESIZE)
      {   // free an empty page
	  kma_page_tm* pEmptyPage = pfl->pLatestPage;
	  pfl->pLatestPage = pEmptyPage->pKmaPageL;
	  free_page((kma_page_t*)pEmptyPage);
	  pfl->memRemain -= PAGESIZE;
	  (pfl->pageNo)--;
      }
#if DEBUG
      printf("2$$$$$ memRemain = %d $$$$$\n", pfl->memRemain);
#endif
      if(pfl->memRemain == PAGESIZE - sizeof(pageFreeList))
      {  // free the first page
	 pfl->memRemain = 0;
#if DEBUG
	 printf("1$$$$$ memRemain = %d $$$$$\n", pfl->memRemain);
#endif
	 pfl->pLatestPage = NULL;
	 free_page(pgFirstPage);
	 pgFirstPage = NULL;
      } 
      return;
   }

   headerF* fbl = ptr;
   kma_size_t maskSize = setFreeMask(size);;
   fbl->size = maskSize; // set the header of the free memblock
   // set the footer of the free memblock
   *(kma_size_t*)((char*)fbl + size - sizeof(kma_size_t)) = maskSize;
#if DEBUG
   printf("Before Insert Ptr: %p Size: %x\n", ptr, size);
#endif
   FreeListInsert(ptr, size);
#if DEBUG
   printFreeList(); // DEBUG
#endif
   return;
}

#endif // KMA_RM


/* Improvement Opportunity
 *   - NEXTPTR *** maybe for debugging
 *   - pageNo 
 *   - sort the free list from high to low address 
 *   - sort the free list with memory size (high first low last)
 *   - if the size is larger than PAGESIZE/2 
 *   - search the free list from the first pointer 
 *   - Otherwise, search the free list from the last pointer 
 *   - delete the unused variables such as memBlockSize in malloc to 
 *          and keep it values in size
 *   - delete the unnecessary initialization such as lines 294-296
 *   - reduce the pointer arithemetic as much as possible 
 *          by keeping their values in the local variable
 *   - do not forget the optimization flags
 *   - isFreeL and isFreeR 
 *   - erase all non essential assert
 */
